|
In computer science, lattice problems are a class of optimization problems on lattices. The conjectured intractability of such problems is central to construction of secure lattice-based cryptosystems. For applications in such cryptosystems, lattices over vector spaces (often ) or free modules (often ) are generally considered. For all the problems below, assume that we are given (in addition to other more specific inputs) a basis for the vector space ''V'' and a norm ''N''. The norms usually considered are ''L''2. However, other norms (such as ''L''p) are also considered and show up in a variety of results. Let denote the length of the shortest non-zero vector in the lattice ''L'', that is, : . ==Shortest vector problem (SVP)== In SVP, a basis of a vector space ''V'' and a norm ''N'' (often ''L''2) are given for a lattice ''L'' and one must find the shortest non-zero vector in ''V'', as measured by ''N'', in ''L''. In other words, the algorithm should output a non-zero vector ''v'' such that . In the -approximation version , one must find a non-zero lattice vector of length at most . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lattice problem」の詳細全文を読む スポンサード リンク
|